package com.Sep_SevenTeen;

import java.util.*;


/**
 * 827. 最大人工岛
 * 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
 *
 * 返回执行此操作后，grid 中最大的岛屿面积是多少？
 *
 * 岛屿 由一组上、下、左、右四个方向相连的 1 形成。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/making-a-large-island
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution827 {

    int count;
    static int[][] dir=new int[][]{
            {0,1},
            {1,0},
            {-1,0},
            {0,-1}
    };

    public void dfs(int[][] grid, Boolean[][] visited, int x, int y, int mark){
        if (visited[x][y] ||grid[x][y]==0) return;
        visited[x][y]=true;
        grid[x][y]=mark;
        count++;
        for (int i=0;i<4;i++)
        {
            int nextX=x+dir[i][0];
            int nextY=y+dir[i][1];
            if (nextX<0||nextX>=grid.length||nextY<0||nextY>=grid[0].length) continue;
            dfs(grid,visited,nextX,nextY,mark);
        }
    }

    public  int largestIsland(int[][] grid) {

        int n=grid.length,m=grid[0].length;
        Boolean[][] visited=new Boolean[n][m];
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                visited[i][j]=false;
            }
        }
        Map<Integer,Integer>gridNum=new HashMap<>();
        int mark=2;
        boolean isAllLand=true;  //是否全是陆地
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if (grid[i][j]==0) isAllLand=false;
                if (!visited[i][j] &&grid[i][j]==1)
                {
                    count=0;
                    dfs(grid,visited,i,j,mark);
                    gridNum.put(mark,count);
                    mark++;

                }
            }
        }
        if (isAllLand) return n*m;
        int result=0;
        Set<Integer> visitedGrid=new HashSet<>();
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++) {
                int count = 1;
                visitedGrid.clear();
                if (grid[i][j] == 0)
                {
                    for (int k = 0; k < 4; k++) {
                        int nearI = i + dir[k][0];
                        int nearJ = j + dir[k][1];
                        if (nearI < 0 || nearI >= grid.length || nearJ < 0 || nearJ >= grid[0].length) continue;
                        if (visitedGrid.contains(grid[nearI][nearJ])) continue;
                        count += gridNum.getOrDefault(grid[nearI][nearJ],0);
                        visitedGrid.add(grid[nearI][nearJ]);
                    }
                }
                result = Math.max(result, count);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution827 solution827=new Solution827();
        int[][] grid={{0, 0}, {0, 0}};
        System.out.println(Arrays.deepToString(grid));
        System.out.println(solution827.largestIsland(grid));
        System.out.println(Arrays.deepToString(grid));
    }
}
